{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #黑白翻转棋"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: flipChess"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #黑白翻转棋"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "在 `n*m` 大小的棋盘中，有黑白两种棋子，黑棋记作字母 `\"X\"`, 白棋记作字母 `\"O\"`，空余位置记作 `\".\"`。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。\n",
    "\n",
    "\n",
    "\n",
    "![1.gif](https://pic.leetcode-cn.com/1630396029-eTgzpN-6da662e67368466a96d203f67bb6e793.gif){:height=170px}![2.gif](https://pic.leetcode-cn.com/1630396240-nMvdcc-8e4261afe9f60e05a4f740694b439b6b.gif){:height=170px}![3.gif](https://pic.leetcode-cn.com/1630396291-kEtzLL-6fcb682daeecb5c3f56eb88b23c81d33.gif){:height=170px}\n",
    "\n",
    "「力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形成可翻转棋子的棋盘残局，其状态记作 `chessboard`。若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。\n",
    "\n",
    "**注意：**\n",
    "- 若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以 **继续** 翻转白棋\n",
    "- 输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置\n",
    "\n",
    "**示例 1：**\n",
    "> 输入：`chessboard = [\"....X.\",\"....X.\",\"XOOO..\",\"......\",\"......\"]`\n",
    "> \n",
    "> 输出：`3`\n",
    "> \n",
    "> 解释：\n",
    "> 可以选择下在 `[2,4]` 处，能够翻转白方三枚棋子。\n",
    "\n",
    "**示例 2：**\n",
    "> 输入：`chessboard = [\".X.\",\".O.\",\"XO.\"]`\n",
    "> \n",
    "> 输出：`2`\n",
    "> \n",
    "> 解释：\n",
    "> 可以选择下在 `[2,2]` 处，能够翻转白方两枚棋子。\n",
    "![2126c1d21b1b9a9924c639d449cc6e65.gif](https://pic.leetcode-cn.com/1626683255-OBtBud-2126c1d21b1b9a9924c639d449cc6e65.gif)\n",
    "\n",
    "**示例 3：**\n",
    "> 输入：`chessboard = [\".......\",\".......\",\".......\",\"X......\",\".O.....\",\"..O....\",\"....OOX\"]`\n",
    "> \n",
    "> 输出：`4`\n",
    "> \n",
    "> 解释：\n",
    "> 可以选择下在 `[6,3]` 处，能够翻转白方四枚棋子。\n",
    "![803f2f04098b6174397d6c696f54d709.gif](https://pic.leetcode-cn.com/1630393770-Puyked-803f2f04098b6174397d6c696f54d709.gif)\n",
    "\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `1 <= chessboard.length, chessboard[i].length <= 8`\n",
    "- `chessboard[i]` 仅包含 `\".\"、\"O\"` 和 `\"X\"`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fHi6rV](https://leetcode.cn/problems/fHi6rV/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fHi6rV](https://leetcode.cn/problems/fHi6rV/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"....X.\",\"....X.\",\"XOOO..\",\"......\",\"......\"]', '[\".X.\",\".O.\",\"XO.\"]', '[\".......\",\".......\",\".......\",\"X......\",\".O.....\",\"..O....\",\"....OOX\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i: int, j: int) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        cnt += max(abs(x - i), abs(y - j))\n",
    "                        while x != i or y != j:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if a != 0 or b != 0]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i: int, j: int) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        cnt += max(abs(x - i), abs(y - j))\n",
    "                        while x != i or y != j:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if a != 0 or b != 0]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i: int, j: int) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        cnt += max(abs(x - i), abs(y - j))\n",
    "                        while x != i or y != j:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if a != 0 or b != 0]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i, j) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in direction:\n",
    "                    x, y = i + a, j + b\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        cnt += max(abs(x - i), abs(y - j))\n",
    "                        while x != i or y != j:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        direction = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if not (a == 0 and b == 0)]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def inlist(self, p, l):\n",
    "        for pairs in l:\n",
    "            if pairs[0] == p[0] and pairs[1]==p[1]:\n",
    "                return True\n",
    "        return False\n",
    "    def flipChess(self, chessboard):\n",
    "        l = len(chessboard)\n",
    "        w = len(chessboard[0])\n",
    "        D =[[1,1],[1,0],[0,1],[1,-1],[-1,1],[0,-1],[-1,0],[-1,-1]]\n",
    "        MAX = 0\n",
    "        for i in range(l):\n",
    "            for j in range(w):\n",
    "                t = [[i, j]]\n",
    "                if chessboard[i][j] == '.':\n",
    "                    s = 0\n",
    "                    for d in D:\n",
    "                        pos = [i,j]\n",
    "                        s_ = 0\n",
    "                        tmp = []\n",
    "                        while(1):\n",
    "                            pos[0] += d[0]\n",
    "                            pos[1] += d[1]\n",
    "                            if pos[0]<0 or pos[0]>=l or pos[1]<0 or pos[1]>=w:\n",
    "                                break\n",
    "                            elif chessboard[pos[0]][pos[1]]=='.':\n",
    "                                break\n",
    "                            elif chessboard[pos[0]][pos[1]]=='O':\n",
    "                                s_ += 1\n",
    "                                tmp.append(copy.copy(pos))\n",
    "                            else:\n",
    "                                s += s_\n",
    "                                t += tmp\n",
    "                                break\n",
    "                    update = True\n",
    "                    while(update):\n",
    "                        update = False\n",
    "                        for idx, p in enumerate(t,1):\n",
    "                            if idx > 1:\n",
    "                                for d in D:\n",
    "                                    pos = copy.copy(p)\n",
    "                                    s_ = 0\n",
    "                                    tmp = []\n",
    "                                    while (1):\n",
    "                                        pos[0] += d[0]\n",
    "                                        pos[1] += d[1]\n",
    "                                        if pos[0] < 0 or pos[0] >= l or pos[1] < 0 or pos[1] >= w:\n",
    "                                            break\n",
    "                                        elif self.inlist(pos, t):\n",
    "                                            s += s_\n",
    "                                            t += tmp\n",
    "                                            if s_ > 0:\n",
    "                                                update = True\n",
    "                                            break\n",
    "                                        elif chessboard[pos[0]][pos[1]] == '.':\n",
    "                                            break\n",
    "                                        elif chessboard[pos[0]][pos[1]] == 'O':\n",
    "                                            s_ += 1\n",
    "                                            tmp.append(copy.copy(pos))\n",
    "                                        else:\n",
    "                                            s += s_\n",
    "                                            t += tmp\n",
    "                                            if s_ > 0:\n",
    "                                                update = True\n",
    "                                            break\n",
    "                    if s>MAX:\n",
    "                        MAX = s\n",
    "        return MAX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i: int, j: int) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    k = 0\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                        k += 1\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        # cnt += max(abs(x - i), abs(y - j))\n",
    "                        cnt += k\n",
    "                        while k > 0:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "                            k -= 1\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if a != 0 or b != 0]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(0,1), (0,-1), (1,0), (-1,0), (1,1), (-1,-1), (1,-1), (-1,1)]\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if chessboard[i][j] != '.':\n",
    "                    continue\n",
    "                board = chessboard.copy()\n",
    "                queue = collections.deque([(i,j)])\n",
    "                tmp = -1\n",
    "                while queue:\n",
    "                    x, y = queue.popleft()\n",
    "                    tmp += 1\n",
    "                    for dx, dy in dirs:\n",
    "                        tx, ty = x+dx, y+dy\n",
    "                        if not (0 <=tx<m and 0<=ty<n) or board[tx][ty] != 'O':\n",
    "                            continue\n",
    "                        candidates = []\n",
    "                        while 0 <=tx<m and 0<=ty<n:\n",
    "                            if board[tx][ty] == 'O':\n",
    "                                candidates.append((tx,ty))\n",
    "                                tx, ty = tx+dx, ty+dy\n",
    "                            elif board[tx][ty] == '.':\n",
    "                                break\n",
    "                            else:\n",
    "                                for xx, yy in candidates:\n",
    "                                    board[xx]= board[xx][:yy] + \"X\" + board[xx][yy+1:]\n",
    "                                    queue.append((xx, yy))\n",
    "                                break\n",
    "                res = max(res, tmp)\n",
    "\n",
    "        return res    \n",
    "                        \n",
    "\n",
    "                        \n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i: int, j: int) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        cnt += max(abs(x - i), abs(y - j))\n",
    "                        while x != i or y != j:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if a != 0 or b != 0]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i: int, j: int) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        cnt += max(abs(x - i), abs(y - j))\n",
    "                        while x != i or y != j:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if a != 0 or b != 0]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "\n",
    "        def judge(chessboard, x, y, dx, dy):\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "\n",
    "        def bfs(chessboard, px, py):\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            cnt = 0\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = \"X\"\n",
    "\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx + dx, ty + dy\n",
    "                            while chessboard[x][y] != 'X':\n",
    "                                q.append((x,y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx\n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == \".\":\n",
    "                    res = max(res, bfs(chessboard, i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def judge(chessboard: List[List[str]], x: int, y: int, dx: int, dy: int) -> bool:\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "        \n",
    "        def bfs(chessboard: List[str], px: int, py: int) -> int:\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            cnt = 0\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = \"X\"\n",
    "\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx + dx, ty + dy\n",
    "                            while chessboard[x][y] != \"X\":\n",
    "                                q.append((x, y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx\n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == \".\":\n",
    "                    res = max(res, bfs(chessboard, i, j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.chessboard = None\n",
    "        self.directions = [[0, -1], [0, 1], [-1, 0], [1, 0], [-1, -1], [1, 1], [-1, 1], [1, -1]]\n",
    "        self.n = None\n",
    "        self.m = None\n",
    "\n",
    "    def turn(self, r, c, d, turned):\n",
    "        cur_turned = set()\n",
    "        while True:\n",
    "            if not (0<=r<self.n and 0<=c<self.m) or self.chessboard[r][c] == \".\":\n",
    "                return set()\n",
    "            if (r, c) not in turned and self.chessboard[r][c] == \"O\":\n",
    "                cur_turned.add((r, c))\n",
    "            else:\n",
    "                return cur_turned\n",
    "            \n",
    "            r += self.directions[d][0]\n",
    "            c += self.directions[d][1]\n",
    "\n",
    "        \n",
    "    def bfs(self, r, c):\n",
    "        que = {(r,c)}\n",
    "        turned = {(r, c)}\n",
    "        while que:\n",
    "            que1 = set()\n",
    "            for r,c in que:\n",
    "                for i in range(8):\n",
    "                    cur_turned = self.turn(r+self.directions[i][0], c+self.directions[i][1], i, turned)\n",
    "                    que1|=cur_turned\n",
    "                    turned |= cur_turned\n",
    "            que = que1\n",
    "        return len(turned)-1      \n",
    "\n",
    "    def flipChess(self, chessboard: List[str]) -> int: \n",
    "        self.chessboard = chessboard\n",
    "        ret = 0\n",
    "        self.n = len(chessboard)\n",
    "        self.m = len(chessboard[0])\n",
    "        for r in range(self.n):\n",
    "            for c in range(self.m):\n",
    "                if chessboard[r][c] == \".\":\n",
    "                    ret = max(ret, self.bfs(r, c))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def judge(chessboard, x, y, dx, dy): # 判断在(x, y)位置放置棋能不能在(dx, dy)方向上翻转棋子\n",
    "            x += dx\n",
    "            y += dy\n",
    "            nxt = []\n",
    "            while 0 <= x < n and 0 <= y < m and chessboard[x][y] == 'O':\n",
    "                nxt.append([x, y])\n",
    "                x += dx\n",
    "                y += dy\n",
    "            if 0 <= x < n and 0 <= y < m and chessboard[x][y] == 'X':\n",
    "                return nxt\n",
    "            else:\n",
    "                return []\n",
    "        \n",
    "        def bfs(tx, ty) -> int: #在这个位置放棋子能变几个\n",
    "            chess = [list(row) for row in chessboard]\n",
    "            chess[tx][ty] = 'X'\n",
    "            q = deque()\n",
    "            q.append([tx, ty])\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                nx, ny = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        nxt = judge(chess, nx, ny, dx, dy)\n",
    "                        if nxt:\n",
    "                            for x, y in nxt:\n",
    "                                q.append([x, y])\n",
    "                                chess[x][y] = 'X'\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "        res = 0\n",
    "        n, m = len(chessboard), len(chessboard[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if chessboard[i][j] == '.':\n",
    "                    res = max(res, bfs(i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i: int, j: int) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    k = 0\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                        k += 1\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        cnt += k\n",
    "                        while k > 0:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "                            k -= 1\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i,j):\n",
    "            q = deque([(i,j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i,j = q.popleft()\n",
    "                for a,b in dirs:\n",
    "                    x ,y = i+a , j+b\n",
    "                    while 0<=x<m and 0<=y<n and g[x][y]=='O':\n",
    "                        x , y= x+a , y+b\n",
    "                        if 0<=x<m and 0<=y<n and g[x][y] == 'X':\n",
    "                            x , y = x-a , y-b \n",
    "                            cnt += max(abs(x-i),abs(y-j))\n",
    "                            while x!=i or y!=j:\n",
    "                                g[x][y] = 'X'\n",
    "                                q.append((x,y))\n",
    "                                x , y =x-a , y-b \n",
    "            return cnt\n",
    "\n",
    "        m = len(chessboard)\n",
    "        n = len(chessboard[0])\n",
    "        dirs = [(a,b) for a in range(-1,2) for b in range(-1,2) if a!=0 or b != 0]\n",
    "        return max(bfs(i,j) for i in range(m) for j in range(n) if chessboard[i][j] =='.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]\n",
    "        def DFS(chessboard: List[str], row: int, colume: int):\n",
    "            queue = [(row, colume)]\n",
    "            result = 0\n",
    "            while len(queue):\n",
    "                position = queue.pop()\n",
    "                for direction in directions:\n",
    "                    next_row, next_col = position[0] + direction[0], position[1] + direction[1]\n",
    "                    temp = []\n",
    "                    while 0 <= next_row < len(chessboard) and 0 <= next_col < len(chessboard[0]):\n",
    "                        if chessboard[next_row][next_col] == 'X':\n",
    "                            queue.extend(temp)\n",
    "                            result += len(temp)\n",
    "                            for pos in temp:\n",
    "                                str_pos = chessboard[pos[0]]\n",
    "                                arr_pos = list(str_pos)\n",
    "                                arr_pos[pos[1]] = 'X'\n",
    "                                chessboard[pos[0]] = \"\".join(arr_pos)\n",
    "                            break\n",
    "                        elif chessboard[next_row][next_col] == 'O':\n",
    "                            temp.append((next_row, next_col))\n",
    "                            next_row += direction[0]\n",
    "                            next_col += direction[1]\n",
    "                        else:\n",
    "                            break\n",
    "            return result\n",
    "        answer = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == '.':\n",
    "                    answer = max(answer, DFS(chessboard.copy(), i, j))\n",
    "        return answer\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: str) -> int:\n",
    "        dirs = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        \n",
    "        def search(board, i, j):\n",
    "            board[i][j] = \"X\"\n",
    "            ans = 0\n",
    "            for di, dj in dirs:\n",
    "                tmp = []\n",
    "                ni, nj = i, j\n",
    "                while 0 <= (ni := ni + di) < m and 0 <= (nj := nj + dj) < n:\n",
    "                    if board[ni][nj] in \"X.\":\n",
    "                        if board[ni][nj] == \"X\":\n",
    "                            for ti, tj in tmp:\n",
    "                                board[ti][tj] = \"X\"\n",
    "                            ans += len(tmp) + sum(search(board, ti, tj) for ti, tj in tmp)\n",
    "                        break\n",
    "                    tmp.append((ni, nj))\n",
    "            return ans\n",
    "\n",
    "        return max((search(list(map(list, chessboard)), i, j) for i in range(m) for j in range(n) if chessboard[i][j] == \".\"), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i,j):\n",
    "            q = deque([(i,j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i,j = q.popleft()\n",
    "                for a,b in dirs:\n",
    "                    x ,y = i+a , j+b\n",
    "                    while 0<=x<m and 0<=y<n and g[x][y]=='O':\n",
    "                        x , y= x+a , y+b\n",
    "                        if 0<=x<m and 0<=y<n and g[x][y] == 'X':\n",
    "                            x , y = x-a , y-b \n",
    "                            cnt += max(abs(x-i),abs(y-j))\n",
    "                            while x!=i or y!=j:\n",
    "                                g[x][y] = 'X'\n",
    "                                q.append((x,y))\n",
    "                                x , y =x-a , y-b \n",
    "            return cnt\n",
    "\n",
    "        m = len(chessboard)\n",
    "        n = len(chessboard[0])\n",
    "        dirs = [(a,b) for a in range(-1,2) for b in range(-1,2) if a!=0 or b != 0]\n",
    "        return max(bfs(i,j) for i in range(m) for j in range(n) if chessboard[i][j] =='.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "\n",
    "        dirs= [[-1,1],[1,-1],[1,1],[-1,-1],[1,0],[0,1],[-1,0],[0,-1]] #8个方向，顺序无所谓\n",
    "        rm,cm = len(chessboard),len(chessboard[0])\n",
    "\n",
    "        def find(r1,c1,d,v): #把已经翻转过的位置也传进来\n",
    "            res = set()\n",
    "            while True:\n",
    "                r1+=dirs[d][0]\n",
    "                c1+=dirs[d][1]\n",
    "                if not (0<=r1<rm and 0<=c1<cm) or chessboard[r1][c1]=='.': #出界或者空格说明此位置无法翻转\n",
    "                    return set()\n",
    "                if (r1,c1) not in v and chessboard[r1][c1]=='O': #没被翻转过的O才是白棋\n",
    "                    res.add((r1,c1))\n",
    "                else:\n",
    "                    return res\n",
    "        \n",
    "        def bfs(rs,cs):\n",
    "            que = {(rs,cs)}\n",
    "            visited={(rs,cs)}\n",
    "            while que:\n",
    "                que1 = set()\n",
    "                for r,c in que:\n",
    "                    for d in range(8):\n",
    "                        new = find(r,c,d,visited)\n",
    "                        que1|=new #位运算符可以代替循环\n",
    "                        visited|=new\n",
    "                que = que1\n",
    "            return len(visited)-1 #初始落子位置不算在被翻转的棋子数量\n",
    "                \n",
    "        mx = 0\n",
    "        for r in range(rm):\n",
    "            for c in range(cm):\n",
    "                mx = max(mx,bfs(r,c))\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i: int, j: int) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        cnt += max(abs(x - i), abs(y - j))\n",
    "                        while x != i or y != j:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if a != 0 or b != 0]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def checker(chessboard, x, y, dx, dy):\n",
    "            x+=dx\n",
    "            y+=dy\n",
    "            while 0<=x<len(chessboard) and 0<=y<len(chessboard[0]):\n",
    "                if chessboard[x][y]==\"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y]==\".\":\n",
    "                    return False\n",
    "                x+=dx\n",
    "                y+=dy\n",
    "            return False\n",
    "\n",
    "        def bfs(chessboard, px, py):\n",
    "            chessboard=[list(row) for row in chessboard]\n",
    "            counter=0\n",
    "            q=deque([(px,py)])\n",
    "            chessboard[px][py]=\"X\"\n",
    "\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1,0,1]:\n",
    "                    for dy in [-1,0,1]:\n",
    "                        if dx==dy==0:\n",
    "                            continue\n",
    "                        if checker(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx+dx, ty+dy\n",
    "                            while chessboard[x][y]!=\"X\":\n",
    "                                q.append((x,y))\n",
    "                                chessboard[x][y]=\"X\"\n",
    "                                x+=dx\n",
    "                                y+=dy\n",
    "                                counter+=1\n",
    "            return counter\n",
    "\n",
    "\n",
    "        m,n = len(chessboard), len(chessboard[0])\n",
    "        res=0\n",
    "        seen=[[False]*n for _ in range(m)]\n",
    "        dirs=[(i,j) for i in [0,-1,1] for j in [0,-1,1]][1:]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if chessboard[i][j]=='O':\n",
    "                    for dx, dy in dirs:\n",
    "                        x,y=i+dx,j+dy\n",
    "                        if 0<=x<m and 0<=y<n and chessboard[x][y]=='.' and seen[x][y]==False:\n",
    "                            seen[x][y]=True\n",
    "                            res=max(res, bfs(chessboard,x,y))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i: int, j: int) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    k = 0\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                        k += 1\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        # cnt += max(abs(x - i), abs(y - j))\n",
    "                        cnt += k\n",
    "                        while x != i or y != j:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if a != 0 or b != 0]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def judge(chessboard, x, y, dx, dy): # check if current place is a start of an flipping array\n",
    "            x += dx # move a long direction dx dy\n",
    "            y += dy\n",
    "            while 0<= x < len(chessboard) and 0<= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == 'X':\n",
    "                    return True #the array end with another black\n",
    "                elif chessboard[x][y] == '.':\n",
    "                    return False # there is an empty grid\n",
    "                x += dx # keep moving\n",
    "                y += dy\n",
    "            return False # return False if it is not ended with black\n",
    "\n",
    "        def countFlip(chessboard:list[str], px, py):\n",
    "            chessboard = [list(row) for row in chessboard] # start with initial chessboard\n",
    "            count = 0\n",
    "            queue = deque([(px, py)]) # double ended queue\n",
    "            chessboard[px][py] = \"X\" # current is black\n",
    "            while queue:\n",
    "                px, py = queue.popleft() # check next new black\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, px, py, dx, dy): # check if there are white pieces to flip \n",
    "                            #print(queue, px, py, dx, dy)\n",
    "                            x, y = px + dx, py + dy\n",
    "                            #print(queue, x, y, dx, dy)\n",
    "                            while chessboard[x][y] != \"X\":\n",
    "                                queue.append((x,y)) # append it to the next check list\n",
    "                                chessboard[x][y] = \"X\" # color the white black\n",
    "                                x += dx # move to the next chess\n",
    "                                y += dy\n",
    "                                count += 1\n",
    "                                #print(x, y, dx, dy, count)\n",
    "\n",
    "                        #print(queue)\n",
    "            return count\n",
    "\n",
    "        res = 0\n",
    "        for x in range(len(chessboard)):\n",
    "            for y in range(len(chessboard[0])):\n",
    "                if chessboard[x][y] == '.':\n",
    "                    res = max(res, countFlip(chessboard, x, y))\n",
    "                    #print(x, y, countFlip(chessboard, x, y))\n",
    "        return res\n",
    "        \n",
    "        #print(chessboard[2][4])\n",
    "        #print(countFlip(chessboard, 2, 4))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "DIR = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def check(board, r, c):\n",
    "            board[r][c] = 'X'\n",
    "            changed = []\n",
    "            for rs, cs in DIR:  # 八方向\n",
    "                nr, nc, tochange = r, c, []\n",
    "                while 0 <= (nr := nr + rs) < m and 0 <= (nc := nc + cs) < n and board[nr][nc] == 'O':  # 探索白色\n",
    "                    tochange.append((nr, nc))  # 记录白色\n",
    "                if tochange and 0 <= nr < m and 0 <= nc < n and board[nr][nc] == 'X':  # 有可翻的白色\n",
    "                    changed += tochange  # 记录翻棋\n",
    "                    for rr, cc in tochange:  # 翻面\n",
    "                        board[rr][cc] = 'X'\n",
    "            return len(changed) + sum(check(board, r, c) for r, c in changed)  # 递归继续检查\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        return max(check(list(map(list, chessboard)), r, c) for r in range(m) for c in range(n) if chessboard[r][c] == '.')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def check(chessboard,tx,ty,dx,dy):\n",
    "            tx += dx \n",
    "            ty += dy\n",
    "            while 0 <= tx < len(chessboard) and 0 <=ty< len(chessboard[0]):\n",
    "                if chessboard[tx][ty] == 'X':\n",
    "                    return True \n",
    "                if chessboard[tx][ty] == '.':\n",
    "                    return False \n",
    "                \n",
    "                tx += dx \n",
    "                ty += dy \n",
    "            \n",
    "            return False \n",
    "        \n",
    "        def bfs(chessboard,x,y):\n",
    "            chessboard = [list(i) for i in chessboard]\n",
    "            chessboard[x][y] = 'X'\n",
    "            cnt = 0 \n",
    "            q = deque([(x,y)])\n",
    "\n",
    "            while q:\n",
    "                tx,ty = q.popleft()\n",
    "                for dx in [-1,0,1]:\n",
    "                    for dy in [-1,0,1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if check(chessboard,tx,ty,dx,dy):\n",
    "                            x,y = tx+dx,ty+dy\n",
    "                            while chessboard[x][y] != 'X':\n",
    "                                q.append((x,y))\n",
    "                                chessboard[x][y] = 'X'\n",
    "                                x += dx \n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "            \n",
    "        ans = 0 \n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == '.':\n",
    "                    ans = max(ans,bfs(chessboard,i,j))\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        def judge(chessboard: List[List[str]], x: int, y: int, dx: int, dy: int) -> bool:\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/fHi6rV/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        def bfs(chessboard, px, py):\n",
    "            cnt = 0\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = 'X'\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for dx in (-1, 0, 1):\n",
    "                    for dy in (-1, 0, 1):\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, x, y, dx, dy):\n",
    "                            tx = x + dx\n",
    "                            ty = y + dy\n",
    "                            while chessboard[tx][ty] != 'X':\n",
    "                                cnt += 1\n",
    "                                q.append((tx, ty))\n",
    "                                chessboard[tx][ty] = 'X'\n",
    "                                tx += dx\n",
    "                                ty += dy\n",
    "            return cnt\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if chessboard[i][j] == '.':\n",
    "                    ans = max(ans, bfs(chessboard, i, j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "\n",
    "        def judge(chessboard, x, y, dx, dy):\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "\n",
    "        def bfs(chessboard, px, py):\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            cnt = 0\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = \"X\"\n",
    "\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx + dx, ty + dy\n",
    "                            while chessboard[x][y] == 'O':\n",
    "                                q.append((x,y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx\n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == \".\":\n",
    "                    res = max(res, bfs(chessboard, i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "        def dfs(i, j):\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        cnt += max(abs(x - i), abs(y - j))\n",
    "                        while x != i or y != j:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "            return cnt\n",
    "        \n",
    "        return max(dfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        m,n = len(chessboard), len(chessboard[0])\n",
    "        def flip(x,y,dx,dy, chessboard):\n",
    "            cur_x, cur_y = x+dx,y+dy\n",
    "            while 0<=cur_x<m and 0<=cur_y<n:\n",
    "                if chessboard[cur_x][cur_y]=='X':\n",
    "                    return True\n",
    "                if chessboard[cur_x][cur_y]=='.':\n",
    "                    return False\n",
    "                cur_x+=dx\n",
    "                cur_y+=dy\n",
    "            return False\n",
    "\n",
    "        def bfs(x,y, chessboard):\n",
    "            cnt = 0\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            chessboard[x][y]='X'\n",
    "            q = deque([(x,y)])\n",
    "            while q:\n",
    "                cur_x, cur_y = q.popleft()\n",
    "                for dx in [-1,0,1]:\n",
    "                    for dy in [-1,0,1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if flip(cur_x, cur_y, dx,dy, chessboard):\n",
    "                            flip_x = cur_x+dx\n",
    "                            flip_y = cur_y+dy\n",
    "                            while chessboard[flip_x][flip_y]!='X':\n",
    "                                chessboard[flip_x][flip_y] = 'X'\n",
    "                                q.append((flip_x,flip_y))\n",
    "                                cnt+=1\n",
    "                                flip_x+=dx\n",
    "                                flip_y+=dy\n",
    "            return cnt\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if chessboard[i][j]=='.':\n",
    "                    ans = max(ans, bfs(i,j, chessboard))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def juede(chessboard,x,y,dx,dy):\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < n and 0 <= y < m:\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "\n",
    "            return False\n",
    "\n",
    "\n",
    "        def bfs(chessboard,px,py):\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            cnt = 0\n",
    "            q = deque([(px,py)])\n",
    "            chessboard[px][py] = \"X\"\n",
    "\n",
    "            while q:\n",
    "                tx,ty = q.popleft()\n",
    "                for dx in [-1,0,1]:\n",
    "                    for dy in [-1,0,1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if juede(chessboard,tx,ty,dx,dy):\n",
    "                            x,y = tx + dx,ty + dy\n",
    "                            while chessboard[x][y] != \"X\":\n",
    "                                q.append((x,y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx\n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            \n",
    "            return cnt\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        n,m = len(chessboard),len(chessboard[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if chessboard[i][j] == '.':\n",
    "                    res = max(res,bfs(chessboard,i,j))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "\n",
    "        dirs= [[-1,1],[1,-1],[1,1],[-1,-1],[1,0],[0,1],[-1,0],[0,-1]] #8个方向，顺序无所谓\n",
    "        rm,cm = len(chessboard),len(chessboard[0])\n",
    "\n",
    "        def find(r1,c1,d,v): #把已经翻转过的位置也传进来\n",
    "            res = set()\n",
    "            while True:\n",
    "                r1+=dirs[d][0]\n",
    "                c1+=dirs[d][1]\n",
    "                if not (0<=r1<rm and 0<=c1<cm) or chessboard[r1][c1]=='.': #出界或者空格说明此位置无法翻转\n",
    "                    return set()\n",
    "                if (r1,c1) not in v and chessboard[r1][c1]=='O': #没被翻转过的O才是白棋\n",
    "                    res.add((r1,c1))\n",
    "                else:\n",
    "                    return res\n",
    "        \n",
    "        def bfs(rs,cs):\n",
    "            que = {(rs,cs)}\n",
    "            visited={(rs,cs)}\n",
    "            while que:\n",
    "                que1 = set()\n",
    "                for r,c in que:\n",
    "                    for d in range(8):\n",
    "                        new = find(r,c,d,visited)\n",
    "                        que1|=new #位运算符可以代替循环\n",
    "                        visited|=new\n",
    "                que = que1\n",
    "            return len(visited)-1 #初始落子位置不算在被翻转的棋子数量\n",
    "                \n",
    "        mx = 0\n",
    "        for r in range(rm):\n",
    "            for c in range(cm):\n",
    "                mx = max(mx,bfs(r,c))\n",
    "        return mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def count(i, j):\n",
    "            board = [list(row) for row in chessboard]\n",
    "            board[i][j] = 'X'\n",
    "            queue = deque([(i, j)])\n",
    "\n",
    "            count_flip = 0\n",
    "            while queue:\n",
    "                i, j = queue.popleft()\n",
    "                for x, y in [(-1, 0), (1, 0), (0, 1), (0, -1), \n",
    "                (1, 1), (-1, -1), (-1, 1), (1, -1)]:\n",
    "                    t = 1\n",
    "                    final_t = 1\n",
    "                    while 0 <= i + t * x < n and 0 <= j + t * y < m \\\n",
    "                    and board[i + t * x][j + t * y] != '.':\n",
    "                        if board[i + t * x][j + t * y] == 'X':\n",
    "                            final_t = t\n",
    "                            break\n",
    "                        t += 1\n",
    "                    while final_t > 1:\n",
    "                        final_t -= 1\n",
    "                        board[i + final_t * x][j + final_t * y] = 'X'\n",
    "                        count_flip += 1\n",
    "                        queue.append((i + final_t * x, j + final_t * y))\n",
    "            return count_flip\n",
    "\n",
    "        n = len(chessboard)\n",
    "        m = len(chessboard[0])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if chessboard[i][j] == '.':\n",
    "                    ans = max(ans, count(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        n, m = len(chessboard), len(chessboard[0])\n",
    "        max_flip = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if chessboard[i][j] != \".\":\n",
    "                    continue\n",
    "                board = [[c for c in row] for row in chessboard]\n",
    "                q, head = [[i, j]], -1\n",
    "                visited = [[False] * m for _ in range(n)]\n",
    "                visited[i][j] = True\n",
    "                while head + 1 < len(q):\n",
    "                    head += 1\n",
    "                    x, y = q[head]\n",
    "                    for dx in range(-1, 2):\n",
    "                        for dy in range(-1, 2):\n",
    "                            if dx == 0 and dy == 0:\n",
    "                                continue\n",
    "                            tx, ty = x + dx, y + dy\n",
    "                            while (\n",
    "                                tx >= 0\n",
    "                                and tx < n\n",
    "                                and ty >= 0\n",
    "                                and ty < m\n",
    "                                and board[tx][ty] == \"O\"\n",
    "                            ):\n",
    "                                tx += dx\n",
    "                                ty += dy\n",
    "                            if (\n",
    "                                tx >= 0\n",
    "                                and tx < n\n",
    "                                and ty >= 0\n",
    "                                and ty < m\n",
    "                                and board[tx][ty] == \"X\"\n",
    "                            ):\n",
    "                                tx, ty = x + dx, y + dy\n",
    "                                while (\n",
    "                                    tx >= 0\n",
    "                                    and tx < n\n",
    "                                    and ty >= 0\n",
    "                                    and ty < m\n",
    "                                    and board[tx][ty] == \"O\"\n",
    "                                ):\n",
    "                                    board[tx][ty] = \"X\"\n",
    "                                    if not visited[tx][ty]:\n",
    "                                        q.append([tx, ty])\n",
    "                                        visited[tx][ty] = True\n",
    "                max_flip = max(max_flip, len(q) - 1)\n",
    "        return max_flip"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def judge(chessboard: List[List[str]], x: int, y: int, dx: int, dy: int) -> bool:\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "        \n",
    "        def bfs(chessboard: List[str], px: int, py: int) -> int:\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            cnt = 0\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = \"X\"\n",
    "\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx + dx, ty + dy\n",
    "                            while chessboard[x][y] != \"X\":\n",
    "                                q.append((x, y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx\n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == \".\":\n",
    "                    res = max(res, bfs(chessboard, i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        def jundge(chessboard, x, y, dx, dy):\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < m and 0 <= y < n:\n",
    "                if chessboard[x][y] == 'X':\n",
    "                    return True\n",
    "                elif chessboard[x][y] == '.':\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "        def bfs(chessboard, px, py):\n",
    "            cnt = 0\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = 'X'\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for dx in (-1, 0, 1):\n",
    "                    for dy in (-1, 0, 1):\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if jundge(chessboard, x, y, dx, dy):\n",
    "                            tx = x + dx\n",
    "                            ty = y + dy\n",
    "                            while chessboard[tx][ty] != 'X':\n",
    "                                cnt += 1\n",
    "                                q.append((tx, ty))\n",
    "                                chessboard[tx][ty] = 'X'\n",
    "                                tx += dx\n",
    "                                ty += dy\n",
    "            return cnt\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if chessboard[i][j] == '.':\n",
    "                    ans = max(ans, bfs(chessboard, i, j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def judge(chessboard: List[List[str]], x: int, y: int, dx: int, dy: int) -> bool:\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "        \n",
    "        def bfs(chessboard: List[str], px: int, py: int) -> int:\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            cnt = 0\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = \"X\"\n",
    "\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx + dx, ty + dy\n",
    "                            while chessboard[x][y] != \"X\":\n",
    "                                q.append((x, y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx\n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == \".\":\n",
    "                    res = max(res, bfs(chessboard, i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def df(self,i,j,chessboard):\n",
    "        step=[[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]]\n",
    "        res = 0\n",
    "        tmp = [list(i) for i in chessboard]\n",
    "        m = len(tmp[0])\n",
    "        n = len(tmp)\n",
    "        q=deque()\n",
    "        q.append([i,j])\n",
    "        while q:\n",
    "            node=q.popleft()\n",
    "            x=node[0]\n",
    "            y=node[1]\n",
    "            for s,t in step:\n",
    "                a=x+s\n",
    "                b=y+t\n",
    "                cont=0\n",
    "                while 0<=a<n and 0<=b<m and tmp[a][b]=='O':\n",
    "                    cont+=1\n",
    "                    a =a + s\n",
    "                    b =b + t\n",
    "                if 0<=a<n and 0<=b<m and tmp[a][b]=='X':\n",
    "                    res+=cont\n",
    "                    a =a - s\n",
    "                    b =b - t\n",
    "                    while a!=x or b!=y:\n",
    "                        \n",
    "                        q.append([a,b])\n",
    "                        tmp[a][b]='X'\n",
    "                        a = a - s\n",
    "                        b = b - t\n",
    "\n",
    "\n",
    "        return res\n",
    "\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        result=0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j]=='.':\n",
    "                    result=max(result,self.df(i,j,chessboard))\n",
    "        return result\n",
    "   \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "\n",
    "        res = 0\n",
    "        row = len(chessboard)\n",
    "        col = len(chessboard[0])\n",
    "\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if chessboard[r][c] == '.': # if empty, check the result when putting black stone here\n",
    "                    res = max(res, self.bfs(chessboard, r, c))\n",
    "\n",
    "        return res \n",
    "        \n",
    "    def bfs(self, board, r, c):\n",
    "        \"\"\"\n",
    "        given a point, search eight directions\n",
    "        \"\"\"\n",
    "        new_board = [list(board[i]) for i in range(len(board))]\n",
    "        new_board[r][c] = 'X' \n",
    "        queue = deque()\n",
    "        queue.append([r, c]) \n",
    "\n",
    "        directions = ((-1, 0), (1, 0), (0, 1), (0, -1), (-1, 1), (-1, -1), (1, -1), (1, 1))\n",
    "        count = 0\n",
    "\n",
    "        while queue: \n",
    "            cur_r, cur_c = queue.popleft() \n",
    "            for dr, dc in directions:\n",
    "                if self.canFlip(dr, dc, cur_r, cur_c, new_board):\n",
    "                    w_r = cur_r + dr \n",
    "                    w_c = cur_c + dc \n",
    "                    while new_board[w_r][w_c] != 'X':\n",
    "                        queue.append([w_r, w_c])\n",
    "                        new_board[w_r][w_c] = 'X'\n",
    "                        w_r += dr \n",
    "                        w_c += dc \n",
    "                        count += 1\n",
    "        return count \n",
    "\n",
    "    def canFlip(self, dr, dc, r, c, board):\n",
    "        r += dr \n",
    "        c += dc \n",
    "        while 0 <= r < len(board) and 0 <= c < len(board[0]):\n",
    "            if board[r][c] == 'X':\n",
    "                return True \n",
    "            elif board[r][c] == '.':\n",
    "                return False \n",
    "            r += dr \n",
    "            c += dc \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "\n",
    "        def judge(chessboard, x, y, dx, dy):\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "\n",
    "        def bfs(chessboard, px, py):\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            cnt = 0\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = \"X\"\n",
    "\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx + dx, ty + dy\n",
    "                            while chessboard[x][y] == 'O':\n",
    "                                q.append((x,y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx\n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == \".\":\n",
    "                    res = max(res, bfs(chessboard, i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def judge(chessboard: List[List[str]], x: int, y: int, dx: int, dy: int) -> bool:\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "        \n",
    "        def bfs(chessboard: List[str], px: int, py: int) -> int:\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            cnt = 0\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = \"X\"\n",
    "\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx + dx, ty + dy\n",
    "                            while chessboard[x][y] != \"X\":\n",
    "                                q.append((x, y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx\n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == \".\":\n",
    "                    res = max(res, bfs(chessboard, i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def judge(chessboard: List[List[str]], x: int, y: int, dx: int, dy: int) -> bool:\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "        \n",
    "        def bfs(chessboard: List[str], px: int, py: int) -> int:\n",
    "\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            cnt = 0\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = \"X\"\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx + dx, ty + dy\n",
    "                            while chessboard[x][y] != \"X\":\n",
    "                                q.append((x, y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx\n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == \".\":\n",
    "                    res = max(res, bfs(chessboard, i, j))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        def bfs(i: int, j: int) -> int:\n",
    "            q = deque([(i, j)])\n",
    "            g = [list(row) for row in chessboard]\n",
    "            g[i][j] = 'X'\n",
    "            cnt = 0\n",
    "            while q:\n",
    "                i, j = q.popleft()\n",
    "                for a, b in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    while 0 <= x < m and 0 <= y < n and g[x][y] == 'O':\n",
    "                        x, y = x + a, y + b\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 'X':\n",
    "                        x, y = x - a, y - b\n",
    "                        cnt += max(abs(x - i), abs(y - j))\n",
    "                        while x != i or y != j:\n",
    "                            g[x][y] = 'X'\n",
    "                            q.append((x, y))\n",
    "                            x, y = x - a, y - b\n",
    "            return cnt\n",
    "\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        dirs = [(a, b) for a in range(-1, 2) for b in range(-1, 2) if a != 0 or b != 0]\n",
    "        return max(bfs(i, j) for i in range(m) for j in range(n) if chessboard[i][j] == '.')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "\n",
    "        def judge(chessboard, x, y, dx, dy):\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "\n",
    "        def bfs(chessboard, px, py):\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            cnt = 0\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = \"X\"\n",
    "\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx + dx, ty + dy\n",
    "                            while chessboard[x][y] == 'O':\n",
    "                                q.append((x,y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx\n",
    "                                y += dy\n",
    "                                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == \".\":\n",
    "                    res = max(res, bfs(chessboard, i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self,chessboard) -> int:\n",
    "        # chessboard = [\"....X.\",\"....X.\",\"XOOO..\",\"......\",\"......\"]\n",
    "        chess=[list(row) for row in chessboard]\n",
    "        # 8个方向\n",
    "        dirs=[(a,b) for a in range(-1,2) for b in range(-1,2) if a!=0 or b!=0]\n",
    "        res=0\n",
    "        m,n=len(chess),len(chess[0])\n",
    "\n",
    "        return max(self.bfs(i,j,chess,dirs) for i in range(m) for j in range(n))\n",
    "\n",
    "    def bfs(self,i,j,chess,dirs):\n",
    "        if chess[i][j] in [\"X\",\"O\"]:\n",
    "            return 0\n",
    "        m,n=len(chess),len(chess[0])\n",
    "        copyChess=copy.deepcopy(chess)\n",
    "        copyChess[i][j]=\"X\"\n",
    "        cnt=0\n",
    "        total=0\n",
    "        q=collections.deque([(i,j)])\n",
    "        while q:\n",
    "            x,y=q.popleft()\n",
    "            print(x,y)\n",
    "            for dx,dy in dirs:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                while xx in range(m) and yy in range(n) and copyChess[xx][yy]!=\".\":\n",
    "                    if copyChess[xx][yy]==\"O\":\n",
    "                        cnt+=1\n",
    "                        xx+=dx\n",
    "                        yy+=dy\n",
    "                    elif copyChess[xx][yy]==\"X\":\n",
    "                        total+=cnt\n",
    "                        \n",
    "                        xx-=dx\n",
    "                        yy-=dy\n",
    "                        while x!=xx or y!=yy:\n",
    "                            copyChess[xx][yy]=\"X\"\n",
    "                            q.append((xx,yy))\n",
    "                            xx-=dx\n",
    "                            yy-=dy\n",
    "                        break\n",
    "                cnt=0\n",
    "        for row in copyChess:\n",
    "            print(row)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        chessboard = [list(s) for s in chessboard]\n",
    "        m = len(chessboard)\n",
    "        n = len(chessboard[0])\n",
    "        if m <= 2 and n <= 2:\n",
    "            return 0\n",
    "        ns = 0\n",
    "\n",
    "        def neighbor(i, j, direct):\n",
    "            nonlocal ns\n",
    "            ns += 1\n",
    "            di = [-1, -1, 0, 1, -1, 0, 1, 1]\n",
    "            dj = [0, 1, 1, 1, -1, -1, -1, 0]\n",
    "\n",
    "            i += di[direct]\n",
    "            j += dj[direct]\n",
    "            return i, j\n",
    "\n",
    "        def can_reverse(i, j, direct):\n",
    "            ii, jj = neighbor(i, j, direct)\n",
    "            if ii < 0 or ii == m or jj < 0 or jj == n:\n",
    "                return False\n",
    "            if chessboard[ii][jj] != 'O':\n",
    "                return False\n",
    "\n",
    "            while 0 <= ii<m and 0 <= jj < n and chessboard[ii][jj] == 'O':\n",
    "                ii, jj = neighbor(ii, jj, direct)\n",
    "            if ii < 0 or ii == m or jj < 0 or jj == n:\n",
    "                return False\n",
    "            if chessboard[ii][jj] != 'X':\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        q = deque()\n",
    "        res = 0\n",
    "\n",
    "        def reverse_from(i, j):\n",
    "            c = 0\n",
    "            for direct in range(8):\n",
    "                if can_reverse(i, j, direct):\n",
    "                    ii, jj = neighbor(i, j, direct)\n",
    "                    while chessboard[ii][jj] != 'X':\n",
    "                        chessboard[ii][jj] = 'X'\n",
    "                        c += 1\n",
    "                        q.append((ii, jj))\n",
    "                        ii, jj = neighbor(ii, jj, direct)\n",
    "                    ei, ej = ii, jj\n",
    "                    ii, jj = neighbor(i, j, direct)\n",
    "                    while ii != ei or jj != ej:\n",
    "                        c += reverse_from(ii, jj)\n",
    "                        ii, jj = neighbor(ii, jj, direct)\n",
    "            return c\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if chessboard[i][j] != '.':\n",
    "                    continue\n",
    "                count = reverse_from(i, j)\n",
    "                res = max(count, res)\n",
    "                for ii, jj in q:\n",
    "                    chessboard[ii][jj] = 'O'\n",
    "        print(f\"neighbor called {ns} times\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def testFlip(self, chessboard: List[str]) -> List[str]:\n",
    "        m=len(chessboard)\n",
    "        n=len(chessboard[0])\n",
    "        for ii in range(m):\n",
    "            s=''\n",
    "            jjtmp = inf\n",
    "            for jj in range(n):\n",
    "                if chessboard[ii][jj] == 'X' and s == '':\n",
    "                    s = 'X'\n",
    "                elif chessboard[ii][jj] == 'O' and s != '':\n",
    "                    s += 'O'\n",
    "                    jjtmp = min(jjtmp,jj)\n",
    "                elif chessboard[ii][jj] == 'X' and s[-1] == 'O':\n",
    "                    print(ii)\n",
    "                    for kk in range(jjtmp,jj):\n",
    "                        chessboard[ii] = chessboard[ii][0:kk] + 'X' + chessboard[ii][kk+1:]\n",
    "                    jjtmp = inf\n",
    "                    s=''\n",
    "                elif chessboard[ii][jj] == '.':\n",
    "                    s = ''\n",
    "        for jj in range(n):\n",
    "            s=''\n",
    "            iitmp = inf\n",
    "            for ii in range(m):\n",
    "                if chessboard[ii][jj] == 'X' and s == '':\n",
    "                    s = 'X'\n",
    "                elif chessboard[ii][jj] == 'O' and s != '':\n",
    "                    s += 'O'\n",
    "                    iitmp = min(iitmp,ii)\n",
    "                elif chessboard[ii][jj] == 'X' and s[-1] == 'O':\n",
    "                    for kk in range(iitmp,ii):\n",
    "                        chessboard[kk] = chessboard[kk][0:jj] + 'X' + chessboard[kk][jj+1:]\n",
    "                    iitmp = inf\n",
    "                    s=''\n",
    "                elif chessboard[ii][jj] == '.':\n",
    "                    s = ''\n",
    "        for ii in range(-n+3,m):\n",
    "            s=''\n",
    "            jjtmp = inf\n",
    "            for jj in range(n):\n",
    "                if ii+jj<m and ii+jj>=0:\n",
    "                    if chessboard[ii+jj][jj] == 'X' and s == '':\n",
    "                        s = 'X'\n",
    "                    elif chessboard[ii+jj][jj] == 'O' and s != '':\n",
    "                        s += 'O'\n",
    "                        jjtmp = min(jjtmp,jj)\n",
    "                    elif chessboard[ii+jj][jj] == 'X' and s[-1] == 'O':\n",
    "                        for kk in range(jjtmp,jj):\n",
    "                            chessboard[ii+kk] = chessboard[ii+kk][0:kk] + 'X' + chessboard[ii+kk][kk+1:]\n",
    "                        jjtmp = inf\n",
    "                        s=''\n",
    "                    elif chessboard[ii+jj][jj] == '.':\n",
    "                        s = ''\n",
    "        for ii in range(2,m+n):\n",
    "            s=''\n",
    "            jjtmp = inf\n",
    "            for jj in range(n):\n",
    "                if ii-jj<m and ii-jj>=0:\n",
    "                    if chessboard[ii-jj][jj] == 'X' and s == '':\n",
    "                        s = 'X'\n",
    "                    elif chessboard[ii-jj][jj] == 'O' and s != '':\n",
    "                        s += 'O'\n",
    "                        jjtmp = min(jjtmp,jj)\n",
    "                    elif chessboard[ii-jj][jj] == 'X' and s[-1] == 'O':\n",
    "                        for kk in range(jjtmp,jj):\n",
    "                            chessboard[ii-kk] = chessboard[ii-kk][0:kk] + 'X' + chessboard[ii-kk][kk+1:]\n",
    "                        jjtmp = inf\n",
    "                        s=''\n",
    "                    elif chessboard[ii-jj][jj] == '.':\n",
    "                        s = ''\n",
    "        \n",
    "        return chessboard\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        m=len(chessboard)\n",
    "        n=len(chessboard[0])\n",
    "\n",
    "        nWhite = 0\n",
    "        for rw in chessboard:\n",
    "            for lat in rw:\n",
    "                if lat == 'O':\n",
    "                    nWhite += 1\n",
    "\n",
    "        maxFlip = 0\n",
    "        chessboardTmp = chessboard[:]\n",
    "        for ii in range(m):\n",
    "            for jj in range(n):\n",
    "                if chessboard[ii][jj] == '.':\n",
    "                    chessboardTmp = chessboard[:]\n",
    "                    chessboardTmp[ii] = chessboard[ii][0:jj] + 'X' + chessboard[ii][jj+1:]\n",
    "                    chessboardTmp2 = chessboardTmp[:]\n",
    "                    chessboardTmp2[0] = '?' + chessboardTmp[0][1:]\n",
    "                    while chessboardTmp2 != chessboardTmp:\n",
    "                        chessboardTmp2 = chessboardTmp[:]\n",
    "                        chessboardTmp = self.testFlip(chessboardTmp)\n",
    "                    nWhiteTmp = 0\n",
    "                    for rw in chessboardTmp:\n",
    "                        for lat in rw:\n",
    "                            if lat == 'O':\n",
    "                                nWhiteTmp += 1\n",
    "                    maxFlip = max(maxFlip,nWhite - nWhiteTmp)\n",
    "        \n",
    "\n",
    "\n",
    "        return maxFlip\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        # 黑棋是X\n",
    "        # 白棋是0\n",
    "        # 空余是.\n",
    "\n",
    "        # 只要沿着这个方向搜寻，没有碰到黑棋的就返回false\n",
    "        def judge(chessboard: List[List[str]], x,y,dx,dy):\n",
    "            # dx dy是偏移量\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx \n",
    "                y += dy \n",
    "            return False \n",
    "        \n",
    "        def bfs(chessboard: List[str], px, py):\n",
    "            # 将他分隔开\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            # cnt是数量count的缩写\n",
    "            cnt = 0\n",
    "            # 双头队列\n",
    "            q = deque([(px, py)])\n",
    "\n",
    "            chessboard[px][py] = \"X\"\n",
    "            while q:\n",
    "                tx, ty = q.popleft()\n",
    "                for dx in [-1, 0, 1]:\n",
    "                    for dy in [-1, 0, 1]:\n",
    "                        # 没有偏移的直接跳过\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "\n",
    "                        # 如果这个方向上存在黑棋\n",
    "                        if judge(chessboard, tx, ty, dx, dy):\n",
    "                            x, y = tx + dx, ty + dy \n",
    "                            # 将这个偏移方向上的，不是黑棋的位置加进来\n",
    "                            # 同时把这个方向上不是黑棋的位置置为黑棋\n",
    "                            while chessboard[x][y] != \"X\":\n",
    "                                q.append((x, y))\n",
    "                                chessboard[x][y] = \"X\"\n",
    "                                x += dx \n",
    "                                y += dy \n",
    "\n",
    "                                # 计算翻白棋的数量\n",
    "                                cnt += 1\n",
    "            return cnt \n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(chessboard)):\n",
    "            for j in range(len(chessboard[0])):\n",
    "                if chessboard[i][j] == \".\":\n",
    "                    res = max(res, bfs(chessboard, i, j))\n",
    "        return res "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
